import java.util.List;

/*
 * @lc app=leetcode.cn id=1239 lang=java
 *
 * [1239] 串联字符串的最大长度
 */

// @lc code=start
class Solution {
    //整体上看像是二叉树
    int ans = 0;
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        //字符串只有小写字符，26个，int有32位，故可以把每个字符串的字母映射到数字的每一位上。
        for(String s : arr){
            int mask = 0;
            for (int i = 0; i < s.length(); i++) {
                int temp = s.charAt(i)-'a';
                //需要判断这个s里面有无重复字母
                if(((mask>>temp)&1)==1){//有重复数字
                    mask=0;
                    break;
                }
                mask |= 1<<temp;//把这一位加入mask中
            }
            masks.add(mask);
        }

        backTrace(masks,0,0);
        return ans;
    }
    /**
     * 这里的mask是回溯过程中累积的字符，映射成int值了。
     * @param masks 所有字符串映射而成的int值
     * @param pos 当前遍历到的位置
     * @param mask 代表累加结果
     */
    public void backTrace(List<Integer> masks,int pos,int mask){
        if(pos==masks.size()){
            ans = Math.max(ans, Integer.bitCount(mask));
            return;
        }
        //masks.get(pos)，可以选择加入mask（前提是没有重复字符），可以不加入。
        if((mask & (masks.get(pos)) )==0){//当前累积mask和遍历到的那个字符串的mask没有重复的位，代表可加入
            backTrace(masks, pos+1, mask|masks.get(pos));
        }
        backTrace(masks, pos+1, mask);
    }
}
// @lc code=end

